/*
 * 给你一个整数数组 nums，有一个大小为 k
 * 的滑动窗口从数组的最左侧移动到数组的最右侧。 你只可以看到在滑动窗口内的 k
 * 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
 *
 * 示例 1：
 *   输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 *   输出：[3,3,5,5,6,7]
 *   解释：
 *     滑动窗口的位置                最大值
 *     ---------------               -----
 *     [1  3  -1] -3  5  3  6  7       3
 *      1 [3  -1  -3] 5  3  6  7       3
 *      1  3 [-1  -3  5] 3  6  7       5
 *      1  3  -1 [-3  5  3] 6  7       5
 *      1  3  -1  -3 [5  3  6] 7       6
 *      1  3  -1  -3  5 [3  6  7]      7
 *
 * 示例 2：
 *
 *   输入：nums = [1], k = 1
 *   输出：[1]
 *
 * 提示：
 *
 *   1 <= nums.length <= 105
 *   -104 <= nums[i] <= 104
 *   1 <= k <= nums.length
 */

// gcc -g  main3.c -std=c99 -lm

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
  int prefixMax[numsSize], suffixMax[numsSize];
  for (int i = 0; i < numsSize; ++i) {
    if (i % k == 0) {
      prefixMax[i] = nums[i];
    } else {
      prefixMax[i] = fmax(prefixMax[i - 1], nums[i]);
    }
  }
  for (int i = numsSize - 1; i >= 0; --i) {
    if (i == numsSize - 1 || (i + 1) % k == 0) {
      suffixMax[i] = nums[i];
    } else {
      suffixMax[i] = fmax(suffixMax[i + 1], nums[i]);
    }
  }

  *returnSize = 0;
  int* ans = malloc(sizeof(int) * (numsSize - k + 1));
  for (int i = 0; i <= numsSize - k; ++i) {
    ans[(*returnSize)++] = fmax(suffixMax[i], prefixMax[i + k - 1]);
  }
  return ans;
}

int main() {
  int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
  int k = 3;
  int n = sizeof(nums) / sizeof(nums[0]);
  int returnSize;
  int* result = maxSlidingWindow(nums, n, k, &returnSize);

  printf("Max sliding window: ");
  int i;
  for (i = 0; i < returnSize; ++i) {
    printf("%d ", result[i]);
  }
  printf("\n");

  free(result);
  return 0;
}
